{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Beautiful Towers I"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumSumOfHeights"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #美丽塔 I"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>n</code>&nbsp;下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>maxHeights</code>&nbsp;。</p>\n",
    "\n",
    "<p>你的任务是在坐标轴上建 <code>n</code>&nbsp;座塔。第&nbsp;<code>i</code>&nbsp;座塔的下标为 <code>i</code>&nbsp;，高度为&nbsp;<code>heights[i]</code>&nbsp;。</p>\n",
    "\n",
    "<p>如果以下条件满足，我们称这些塔是 <strong>美丽</strong>&nbsp;的：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>1 &lt;= heights[i] &lt;= maxHeights[i]</code></li>\n",
    "\t<li><code>heights</code>&nbsp;是一个 <strong>山状</strong>&nbsp;数组。</li>\n",
    "</ol>\n",
    "\n",
    "<p>如果存在下标 <code>i</code>&nbsp;满足以下条件，那么我们称数组&nbsp;<code>heights</code>&nbsp;是一个 <strong>山状</strong>&nbsp;数组：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>对于所有&nbsp;<code>0 &lt; j &lt;= i</code>&nbsp;，都有&nbsp;<code>heights[j - 1] &lt;= heights[j]</code></li>\n",
    "\t<li>对于所有&nbsp;<code>i &lt;= k &lt; n - 1</code>&nbsp;，都有&nbsp;<code>heights[k + 1] &lt;= heights[k]</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回满足 <b>美丽塔</b>&nbsp;要求的方案中，<strong>高度和的最大值</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>maxHeights = [5,3,4,1,1]\n",
    "<b>输出：</b>13\n",
    "<b>解释：</b>和最大的美丽塔方案为 heights = [5,3,3,1,1] ，这是一个美丽塔方案，因为：\n",
    "- 1 &lt;= heights[i] &lt;= maxHeights[i]  \n",
    "- heights 是个山状数组，峰值在 i = 0 处。\n",
    "13 是所有美丽塔方案中的最大高度和。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>maxHeights = [6,5,3,9,2,7]\n",
    "<b>输出：</b>22\n",
    "<strong>解释：</strong> 和最大的美丽塔方案为 heights = [3,3,3,9,2,2] ，这是一个美丽塔方案，因为：\n",
    "- 1 &lt;= heights[i] &lt;= maxHeights[i]\n",
    "- heights 是个山状数组，峰值在 i = 3 处。\n",
    "22 是所有美丽塔方案中的最大高度和。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>maxHeights = [3,2,5,5,2,3]\n",
    "<b>输出：</b>18\n",
    "<strong>解释：</strong>和最大的美丽塔方案为 heights = [2,2,5,5,2,2] ，这是一个美丽塔方案，因为：\n",
    "- 1 &lt;= heights[i] &lt;= maxHeights[i]\n",
    "- heights 是个山状数组，最大值在 i = 2 处。\n",
    "注意，在这个方案中，i = 3 也是一个峰值。\n",
    "18 是所有美丽塔方案中的最大高度和。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n == maxHeights &lt;= 10<sup>3</sup></code></li>\n",
    "\t<li><code>1 &lt;= maxHeights[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [beautiful-towers-i](https://leetcode.cn/problems/beautiful-towers-i/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [beautiful-towers-i](https://leetcode.cn/problems/beautiful-towers-i/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,3,4,1,1]', '[6,5,3,9,2,7]', '[3,2,5,5,2,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, A: List[int]) -> int:\n",
    "        \n",
    "        n = len(A)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            tmp = A[i]\n",
    "            prev = A[i]\n",
    "            for left in range(i-1, -1, -1):\n",
    "                p = min(A[left], prev)\n",
    "                prev = p\n",
    "                tmp += p\n",
    "            \n",
    "            prev = A[i]\n",
    "            for right in range(i+1, n):\n",
    "                p = min(A[right], prev)\n",
    "                prev = p\n",
    "                tmp += p\n",
    "        \n",
    "            ans = max(ans, tmp)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(maxHeights)\n",
    "\n",
    "        for i,x in enumerate(maxHeights):\n",
    "            s = mn = x\n",
    "            for j in range(i-1, -1, -1):\n",
    "                mn = min(mn, maxHeights[j])\n",
    "                s += mn\n",
    "            mn = x\n",
    "            for j in range(i+1, n):\n",
    "                mn = min(mn, maxHeights[j])\n",
    "                s += mn\n",
    "            ans = max(ans, s)\n",
    "        \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        ans=0\n",
    "        n=len(maxHeights)\n",
    "        for i,x in enumerate(maxHeights):\n",
    "            s = mn =x\n",
    "            for j in range(i-1,-1,-1):\n",
    "                mn = min(mn,maxHeights[j])\n",
    "                s += mn\n",
    "            mn = x\n",
    "            for j in range(i+1,n):\n",
    "                mn=min(mn,maxHeights[j])\n",
    "                s += mn\n",
    "            ans=max(ans,s)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxheights: List[int]) -> int:\n",
    "        heights=maxheights\n",
    "        sum=0\n",
    "\n",
    "        beauty=maxheights\n",
    "\n",
    "        for i in range(len(maxheights)):\n",
    "            heights=maxheights[:]\n",
    "            for j in range(i+1,len(maxheights)):\n",
    "                if heights[j]>heights[j-1]:\n",
    "                    heights[j]=heights[j-1]\n",
    "            n=i-1\n",
    "            while n>=0:\n",
    "                if heights[n]>heights[n+1]:\n",
    "                    heights[n]=heights[n+1]\n",
    "                n=n-1\n",
    "            temp=0\n",
    "            for x in range(len(heights)):\n",
    "                temp+=heights[x]\n",
    "            \n",
    "            #print(heights)\n",
    "            #print(temp)\n",
    "            #print(sum)\n",
    "            if temp>sum:\n",
    "                sum=temp\n",
    "                beauty=heights[:]\n",
    "            #print(sum)\n",
    "            #print(beauty)\n",
    "\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:\n",
    "        #n=len(maxHeights)\n",
    "        #ans=0\n",
    "        #for i in range(n):\n",
    "        #    j=i-1\n",
    "        #    temp=maxHeights[i]\n",
    "        #    minimum=maxHeights[i]\n",
    "        #    while j>=0:\n",
    "        #        minimum=min(minimum,maxHeights[j])\n",
    "        #        temp+=minimum\n",
    "        #        j-=1\n",
    "        #    j=i+1\n",
    "        #    minimum=maxHeights[i]\n",
    "        #    while j<=n-1:\n",
    "        #        minimum=min(minimum,maxHeights[j])\n",
    "        #        temp += minimum\n",
    "        #        j += 1\n",
    "        #    print(temp)\n",
    "        #    ans=max(ans,temp)\n",
    "        #return ans\n",
    "        n=len(maxHeights)\n",
    "        pre=[0]*(n)\n",
    "        stk=[-1]\n",
    "        s=0\n",
    "        for i,x in enumerate(maxHeights):\n",
    "            while len(stk)>1 and x<=maxHeights[stk[-1]]:\n",
    "                j=stk.pop()\n",
    "                s -= maxHeights[j]*(j-stk[-1])\n",
    "            s += x*(i-stk[-1])\n",
    "            stk.append(i)\n",
    "            pre[i]=s\n",
    "        \n",
    "        suf=[0]*(n+1)\n",
    "        stk=[n]\n",
    "        s=0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while len(stk)>1 and maxHeights[i]<=maxHeights[stk[-1]]:\n",
    "                j=stk.pop()\n",
    "                s -= maxHeights[j]*(stk[-1]-j)\n",
    "            s+=maxHeights[i]*(stk[-1]-i)\n",
    "            stk.append(i)\n",
    "            suf[i]=s\n",
    "        \n",
    "        ans=suf[0]\n",
    "        for i in range(n):\n",
    "            ans=max(ans,pre[i]+suf[i+1])\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
